package com.leetcode.algorithm.y22.m08.w1;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 1091. 二进制矩阵中的最短路径
 * 
 * https://leetcode.cn/problems/shortest-path-in-binary-matrix/
 * 
 * @author jie.deng
 *
 */
class Question1091Solution01 {
	
	public int shortestPathBinaryMatrix(int[][] grid) {
		int rows = grid.length;
		int cols = grid[0].length;
		if (grid[0][0] != 0) {
			return -1;
		}
		if (rows == 1 && cols == 1) {
			return 1;
		}
		Set<Integer> visitedSet = new HashSet<>();
		Queue<int[]> queue = new LinkedList<>();
		int level = 0;
		visitedSet.add(0);
		queue.add(new int[] { 0, 0 });
		int[][] directions = new int[][] { { 1, 1 }, { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }, { 1, -1 }, { -1, -1 },
				{ -1, 1 } };
		while (!queue.isEmpty()) {
			level++;
			int size = queue.size();
			for (int k = 0; k < size; k++) {
				int[] arr = queue.poll();
				int row = arr[0];
				int col = arr[1];
				for (int[] dir : directions) {
					int r = row + dir[0];
					int c = col + dir[1];
					if (r >= 0 && r < rows && c >= 0 && c < cols) {
						if (grid[r][c] == 0) {
							if (r == rows - 1 && c == cols - 1) {
								return level + 1;
							}
							if (visitedSet.add(r * cols + c)) {
								queue.offer(new int[] { r, c });
							}
						}
					}
				}
			}
		}
		return -1;
	}
    
}